import utils from '../utils'

function snapCoords(arcs, threshold) {
  const avgDist = utils.getAvgSegment(arcs)
  const autoSnapDist = avgDist * 0.0025
  let snapDist = autoSnapDist

  if (threshold > 0) {
    snapDist = threshold
    // message(utils.format("Applying snapping threshold of %s -- %.6f times avg. segment length", threshold, threshold / avgDist));
  }
  const snapCount = snapCoordsByInterval(arcs, snapDist)
  if (snapCount > 0) arcs.dedupCoords()
  // message(utils.format("Snapped %s point%s", snapCount, utils.pluralSuffix(snapCount)));
}
// Snap together points within a small threshold
//
function snapCoordsByInterval(arcs, snapDist) {
  let snapCount = 0
  const data = arcs.getVertexData();

  // Get sorted coordinate ids
  // Consider: speed up sorting -- try bucket sort as first pass.
  //
  const ids = sortCoordinateIds(data.xx)
  for (let i=0, n=ids.length; i<n; i++) {
    snapCount += snapPoint(i, snapDist, ids, data.xx, data.yy)
  }
  return snapCount
}
function snapPoint(i, limit, ids, xx, yy) {
  let j = i
  const n = ids.length
  const x = xx[ids[i]]
  const y = yy[ids[i]]
  let snaps = 0
  let id2 = null
  let dx = null
  let dy = null

  while (++j < n) {
    id2 = ids[j]
    dx = xx[id2] - x
    if (dx > limit) break
    dy = yy[id2] - y
    if (dx === 0 && dy === 0 || dx * dx + dy * dy > limit * limit) continue
    xx[id2] = x
    yy[id2] = y
    snaps++
  }
  return snaps
}
function sortCoordinateIds(a) {
  const n = a.length
  const ids = new Uint32Array(n)
  for (let i=0; i<n; i++) {
    ids[i] = i
  }
  quicksortIds(a, ids, 0, ids.length-1)
  return ids
}
function quicksortIds(a, ids, lo, hi) {
  if (hi - lo > 24) {
    const pivot = a[ids[lo + hi >> 1]]
    let i = lo
    let j = hi
    let tmp = null
    while (i <= j) {
      while (a[ids[i]] < pivot) i++
      while (a[ids[j]] > pivot) j--
      if (i <= j) {
        tmp = ids[i]
        ids[i] = ids[j]
        ids[j] = tmp
        i++
        j--
      }
    }
    if (j > lo) quicksortIds(a, ids, lo, j)
    if (i < hi) quicksortIds(a, ids, i, hi)
  } else {
    insertionSortIds(a, ids, lo, hi)
  }
}
function insertionSortIds(arr, ids, start, end) {
  for (let j = start + 1; j <= end; j++) {
    let id = ids[j]
    for (let i = j - 1; i >= start && arr[id] < arr[ids[i]]; i--) {
      ids[i+1] = ids[i]
    }
    ids[i+1] = id
  }
}
export default {
  snapCoords,
}